package com.zjsru.plan2023.oneday.oneDay202301;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: CookLee
 * @Date: 2023/1/14
 * 重排字符形成目标字符串
 *
 * 给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。
 *
 * 从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。
 *
 * 输入：s = "ilovecodingonleetcode", target = "code"
 * 输出：2
 * 解释：
 * 对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
 * 对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
 * 形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
 * 可以形成最多 2 个 "code" 的副本，所以返回 2 。
 *
 *
 * 输入：s = "abcba", target = "abc"
 * 输出：1
 * 解释：
 * 选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。
 * 可以形成最多 1 个 "abc" 的副本，所以返回 1 。
 * 注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。
 *
 * 输入：s = "abbaccaddaeea", target = "aaaaa"
 * 输出：1
 * 解释：
 * 选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
 * 可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。
 */
public class RearrangeCharacters {
    
    /**
     * 重排字符形成目标字符串
     *
     * @param s      输入字符串
     * @param target 目标字符串
     * @return int
     */
    public int rearrangeCharacters(String s, String target) {
        //记录target字符串出现的次数
        Map<Character, Integer> targetMap = new HashMap<>();
        for (int i = 0; i < target.length(); i++) {
            targetMap.put(target.charAt(i), targetMap.getOrDefault(target.charAt(i), 0) + 1);
        }
        //记录s字符串里的字母和target相同的出现次数
        Map<Character, Integer> map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            if (targetMap.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            }
        }
        int cnt = Integer.MAX_VALUE;
        for (Map.Entry<Character, Integer> one : targetMap.entrySet()) {
            Character key = one.getKey();
            Integer value = one.getValue();
            //根据target的字母获取总的出现次数
            Integer step = map.containsKey(key) ? map.get(key) : 0;
            //统计最小重复数，每个字母总数/每个目标字母数
            cnt = Math.min(cnt, step / value);
            if (cnt == 0) {
                return 0;
            }
        }
        return cnt;
    }
    
    public static void main(String[] args) {
        RearrangeCharacters rearrangeCharacters = new RearrangeCharacters();
        String s = "ilovecodingonleetcode";
        String target = "code";
        System.out.println(rearrangeCharacters.rearrangeCharacters(s, target));
    }
}
